package LockingTree;

import java.util.*;

public class Solution {
    class LockingTree {
        List<Integer>[] children;
        int[] lockUser;
        int[] parent;
        public LockingTree(int[] parent) {
            this.parent = parent;
            int n = parent.length;
            this.children = new List[n];
            this.lockUser = new int[n];
            for(int i = 0;i<n;i++) {
                children[i] = new ArrayList();
            }
            for(int i = 0;i<n;i++){
                int p = parent[i];
                if(p!=-1){
                    children[p].add(i);
                }
            }
        }

        public boolean lock(int num, int user) {
            if(lockUser[num]!=0){
                return false;
            }
            lockUser[num] = user;
            return true;
        }

        public boolean unlock(int num, int user) {
            if(lockUser[num]!=user) return false;
            lockUser[num]=0;
            return true;
        }

        public boolean upgrade(int num, int user) {
            if(lockUser[num]!=0)return false;
            if(dfs(num)==false)return false;
            for(int i = num;i>=0;i=parent[i]){
                if(lockUser[i]!=0)return false;
            }
            unlock(num);
            lockUser[num]=user;
            return true;
        }
        private boolean dfs(int root){
            boolean res = lockUser[root]!=0;
            for(int child:children[root]){
                res = res||dfs(child);
            }
            return res;
        }
        // 所有的子节点都变成0
        private void unlock(int num) {
            lockUser[num] = 0;
            for(int child:children[num]) {
                unlock(child);
            }
        }
    }
    public int[][] mergeArrays(int[][] nums1, int[][] nums2) {
        List<int[]> ans = new ArrayList<>();
        int i = 0,j = 0;
        while (i<nums1.length||j<nums2.length){
            int[] t = new int[2];
            if(i == nums1.length) {
                t = nums2[j++];
            } else if (j == nums2.length) {
                t = nums1[i++];
            } else if (nums1[i][0]<nums2[j][0]) {
                t = nums1[i];
                i++;
            } else if (nums1[i][0]>nums2[j][0]){
                t = nums2[j];
                j++;
            } else {
                t = nums1[i];
                t[1]+=nums2[j][1];
                i++;
                j++;
            }
            ans.add(t);
        }
        return ans.toArray(new int[ans.size()][2]);
    }
    public int minNumber(int[] nums1, int[] nums2) {
        // 如果两个数组有交集 返回交集的最小值
        // 否则返回两个数组的最小值的组成
        int[] mask1 = new int[10];
        int min = 10;
        for (int i = 0; i < nums1.length; i++) {
            mask1[nums1[i]] = 1;
            min = Math.min(min,nums1[i]);
        }
        int ans = 100;
        for (int i = 0; i < nums2.length; i++) {
            int t;
            if(mask1[nums2[i]] == 1) {
                t = nums2[i];
            } else {
                // 和最小的组成
                t = Math.min(min*10+nums2[i],nums2[i]*10+min);
            }
            ans = Math.min(ans,t);
        }
        return ans;
    }
    public int[] distinctDifferenceArray(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int[] diff = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
            diff[i] = set.size();
        }
        set.clear();
        for (int i = nums.length-1; i >=0 ; i--) {
            diff[i]-=set.size();
            set.add(nums[i]);
        }
        return diff;
    }
    public int[] circularGameLosers(int n, int k) {
        Set<Integer> set = new HashSet<>();
        int cur = 0;
        int t = k;
        while (!set.contains(cur)) {
            set.add(cur);
            cur = (cur+k)%n; // 传给第i+k个人
            k+=t;
        }
        int[] ans = new int[n-set.size()];
        int index = 0;
        for (int i = 0; i < n; i++) {
            if(!set.contains(i)) {
                ans[index++] = i+1;
            }
        }
        return ans;
    }
    public boolean isFascinating(int n) {
        // n n*2 n*3
        return n == 192 || n == 219 || n == 273 || n == 327;
    }
    public int maxSum(int[] nums) {
        int[] cnt = new int[10];
        int ans = -1;
        for (int num: nums) {
            // 数位上最大的数字相等
            int t = num;
            int max = 0; // 数位上最大数字
            while (t>0){
                max = Math.max(max,t%10);
                t/=10;
            }
            if(cnt[max]!=0) {
                ans = Math.max(ans,cnt[max]+num);
            }
            cnt[max] = Math.max(cnt[max],max);
        }
        return ans;
    }
    public boolean isGood(int[] nums) {
        int n = nums.length-1;
        int[] cnt = new int[n+1];
        for (int num: nums) {
            if(num>n)return false;
            if(cnt[num] == 0) {
                cnt[num] = 1;
            } else {
                if(num!=n) {
                    return false; //
                } else {
                    if(cnt[num] == 2) return false;
                    cnt[num] = 2;
                }
            }
        }
        return cnt[n] == 2;
    }
    public int numberOfPoints(List<List<Integer>> nums) {
        // 差分数组
        int[] cnt = new int[102];
        for (int i = 0; i < nums.size(); i++) {
            cnt[nums.get(i).get(0)]++;
            cnt[nums.get(i).get(1)+1]--;
        }
        int ans = cnt[0] == 0? 0:1;
        for (int i = 1; i < 102; i++) {
            cnt[i]+=cnt[i-1];
            if(cnt[i] > 0) {
                ans++;
            }
        }
        return ans;
    }
    public int minimumSwitchingTimes(int[][] source, int[][] target) {
        // 贪心
        // 能移动就移动 即
        // 看source和target中有多少不一样的
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < source.length; i++) {
            for (int j = 0; j < source[i].length; j++) {
                map.put(source[i][j],map.getOrDefault(source[i][j],0)+1);
            }
        }
        int ans = source.length*source[0].length;
        for (int i = 0; i < target.length; i++) {
            for (int j = 0; j < target[i].length; j++) {
                if(map.getOrDefault(target[i][j],0)>0) {
                   ans--;
                   map.put(target[i][j],map.get(target[i][j])-1);
                }
            }
        }
        return ans;
    }

}
